import java.util.HashMap;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 74646
 * Date: 2022-03-27
 * Time: 15:31
 */

public class HashBuckA {
    //静态类：结点
    static class Node{

        public int key; //存放的元素
        public int val; //元素出现的次数
        public Node next;
        public Node(int key,int val){
            this.key = key;
            this.val = val;
        }
    }
    public Node[] array; //哈希桶是一个 Node类型的数组
    public int usedSize; //元素的个数
    public static final double DEFAULT_LOAD_FACTOR = 0.75; //定义负载因子（负载因子一般情况不能改变）

    public HashBuckA(){
        this.array = new Node[10]; //设置初始容量，未赋值数组中的元素都是null
    }

    /**
     * put方法
     * @param key 元素
     * @param val 元素出现的次数
     */
    public void put(int key,int val){
        //1、找到key所在的位置
        int index = key % this.array.length;

        //2、遍历key所在下标的链表，看是否有相同的key，如果有就更新val值
        Node cur = array[index];
        while (cur!=null){
            if(cur.key==key){
                cur.val = val; //有相同的key，更新val值
            }
            cur = cur.next;
        }

        //3、如果没有这个值就进行结点的插入（头插、尾插都可以）
        //这里使用头插法
        Node node = new Node(key,val);
        node.next = array[index];
        array[index] = node;
        this.usedSize++;

        //尾插
//        Node node = new Node(key,val);
//        if(array[index]==null){
//            array[index] = node;
//        }else {
//            cur = array[index];
//            while (cur.next!=null){
//                cur = cur.next;
//            }
//            cur.next = node;
//        }
//        this.usedSize++;

        //4、插入元素成功之后，检查当前散列表的负载因子
        //如果计算得出的负载因子大于指定的负载因子，那么就进行扩容（增加数组长度降低负载因子）
        if(loadFactor()>DEFAULT_LOAD_FACTOR) {
            resize();
        }
    }

    //扩容
    private void resize1(){
        //扩容需要重新哈希
        Node[] newArray = new Node[array.length*2];
        for (int i = 0; i < array.length; i++) {
            Node cur = array[i];
            while (cur!=null){
                int index = cur.key % newArray.length; //获取扩容后key所在的位置
                //在扩容后的数组中进行头插或尾插(这里使用的是尾插）
                Node curNext = cur.next; //记录原数组中下一个结点的位置
                if(newArray[index]==null){
                    newArray[index] = cur;
                }else{
                    Node newCur = newArray[index];
                    while (newCur.next!=null){
                        newCur = newCur.next;
                    }
                    newCur.next = cur;
                }
                cur = curNext;
            }
        }
        array = newArray; //原数组引用新的数组
    }


    private void resize(){
        //扩容需要重新哈希
        Node[] newArray = new Node[array.length*2];
        for (int i = 0; i < array.length; i++) {
            Node cur = array[i];
            while (cur!=null){
                int index = cur.key % newArray.length; //获取扩容后key所在的位置
                //在扩容后的数组中进行头插或尾插(这里使用的是头插法）
                Node curNext = cur.next; //记录原数组中下一个结点的位置
                cur.next = newArray[index]; //先绑定后面
                newArray[index] = cur; //绑定前面
                cur = curNext;
            }
        }
        array = newArray; //原数组引用新的数组
    }

    //计算负载因子
    private double loadFactor(){
        return 1.0*usedSize / array.length;  //负载因子 = 散列表中的元素个数 / 散列表的长度
    }

    /**
     * 根据key值获取对应的value值
     * @param key 元素
     * @return 返回获取的元素个数
     */
    public int get(int key){
        //1、找到key所在的位置
        int index = key % array.length;
        //2、遍历key所在下标的链表
        Node cur = array[index];
        while (cur!=null){
            if(cur.key==key){
                return cur.val; //找到了就返回对应的value
            }
        }
        return -1; //找到不到就返回-1
    }

public static void main(String[] args) {
    HashBuckA hashBuck = new HashBuckA();
    hashBuck.put(1,1);
    hashBuck.put(12,12);
    hashBuck.put(3,3);
    hashBuck.put(6,6);
    hashBuck.put(7,7);
    hashBuck.put(2,2);
    hashBuck.put(11,11);
    hashBuck.put(8,8);
    hashBuck.put(21,21);
    System.out.println(hashBuck.get(7));
}

}
